package medium

import "strings"

/*
时间复杂度:O(N)
空间复杂度:O(N)

难点：如何将单调栈与k次删除操作联系起来??
解决：如果删除k位数字构建一个最小的数? 高位的数字我们尽可能的希望更小, 可以构建一个非递减的单调栈，
	1.如果当前数字小于栈顶数字,则将栈顶元素弹出,且k减1;
	2.如果最后所有数字遍历完,仍有操作次数,则取stack[:len(stack)-k]即可, 因为stack中肯定是非递减的,越左边的元素越小
	3.对于处理后的前导0,可以通过内置函数去除; 注意要判断最后结果是否为"", 为""则返回"0"

*/

func removeKdigits(num string, k int) string {
	stack := make([]byte, 0)
	for i := range num {
		// 如果当前元素小于栈顶元素,则直接弹出栈,且操作次数-1
		for k > 0 && len(stack) > 0 && num[i] < stack[len(stack)-1] {
			stack = stack[:len(stack)-1]
			k--
		}
		stack = append(stack, num[i])
	}
	result := string(stack[:len(stack)-k])
	result = strings.TrimLeft(result, "0")
	if result == "" {
		return "0"
	}
	return result
}
